#include <stdio.h>
#include <string.h>

typedef struct TreeNode
{
    char data;//数据---对应的字符
    int weight;//权值
    int parent;//父结点
    int lchild;//左孩子
    int rchild;//右孩子
}HTNode;//当不存在父结点或左右孩子时，对应值为-1

//构造哈夫曼树
void CreatHT(HTNode ht[], int n)
{
    int i, k, lnode, ronde;
    double min1, min2;
    for(i = 0; i < 2 * n - 1; i++)//将所有结点初始化, 含n个叶子结点的二叉树共有2*n-1个结点
    {
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    }
    for(i = n; i < 2 * n - 1; i++)//前n个结点为叶子结点, 下标从n到2*n-2的结点都是新产生的结点
    {
        min1 = min2 = 32767;//任意大数，需确保比2*n-1大
        lnode = rnode = -1;
        for(k = 0; k <= i - 1; k++)//遍历已有结点
        {
            if(ht[k].parent == -1)//父结点不为-1的视为已被销毁
            {
                if(ht[k].weight <= min1)//找权值最小的两个结点，同时保证min1(对应左子树lnode)较小
                {
                    min2 = min1;
                    rnode = lnode;
                    min1 = ht[k].weight;
                    lnode = k;
                }
                else if(ht[k].weight <= min2)
                {
                    min2 = ht[k].weight;
                    rnode = k;
                }
            }
        }
        ht[i].weight = ht[lnode].weight + ht[rnode].weight;
        ht[i].lchild = lnode;
        ht[i].rchild = rnode;
        ht[lnode].parent = i;
        ht[rnode].parent = i;
    }
}

//编码本
#define LEN 100 //待编码字符个数
typedef struct 
{
    char ch;          //存储字符
    char code[LEN];   //存放编码(编码长度不会超过字符个数)
}TCode;
TCode CodeBook[LEN];  //编码本

//获得编码本
void encoding(HTNode ht[], TCode book[], int n)
{
    char* str = (char*)malloc(n + 1);
    str[n] = '\0';
    int i, j, idx, p;
    for(i = 0; i < n; i++)//遍历编码本
    {
        book[i].ch = ht[i].ch;
        idx = i;
        j = n;
        while(p = ht[idx].parent > 0)//由底至上访问树，从后向前生成编码
        {
            if(ht[p].lchild == idx)
            {
                j--;
                str[j] = '0';
            }
            else
            {
                j--;
                str[j] = '1';
            }
            idx = p;
        }
        strcpy(book[i].code, &str[j]);
    }
}

//哈夫曼解码算法
void decoding(HTNode ht[], char* codes, int n)
{
    int i, p;
    i = 0;
    p = 2 * n - 2;
    while(codes[i] != '\0')
    {
        while(ht[p].lchild != -1 && ht[p].rchild != -1)
        {
            if(codes[i] == '0')
            p = ht[p].lchild;
            else
            p = ht[p].rchild;
            i++;
        }
        printf("%c", ht[p].ch);
        p = 2 * n - 2;
    }
    printf("\n");
}